#ifndef CLUSNET_BASE_RINGBUFFER_H
#define CLUSNET_BASE_RINGBUFFER_H

#include <clusnet/base/Exception.h>
#include <cstddef>
#include <memory>
#include <cassert>
#include <limits>
#include <stdexcept>

namespace clusnet 
{
namespace base
{

template<class ForwardIterator, class Diff, class T, class Alloc>
inline void uninitialized_fill_n_with_alloc(ForwardIterator first, Diff n, T&& item, Alloc& alloc)
{
    ForwardIterator next = first;
    try
    {
        for (; n > 0; ++first, --n)
        {
            alloc.construct(first, std::forward<T>(item));
        }
    }
    catch (...)
    {
        for (; next != first; ++next)
        {
            alloc.destroy(next);
        }
        throw;
    }
}

template<class Inpuclusneterator, class ForwardIterator, class Alloc>
inline ForwardIterator uninitialized_copy_n_with_alloc(Inpuclusneterator first, Inpuclusneterator last, ForwardIterator dest, Alloc& alloc)
{
    ForwardIterator next = dest;
    try
    {
        for (; first != last; ++first, ++dest)
        {
            alloc.construct(dest, *first);
        }
    }
    catch (...)
    {
        for (; next != dest; ++next)
        {
            alloc.destroy(next);
        }
        throw;
    }
    return dest;
}

template<typename Traits>
struct const_traits
{
    using value_type = typename Traits::value_type;
    using pointer = typename Traits::const_pointer;
    using reference = typename Traits::const_reference;
    using size_type = typename Traits::size_type;
    using difference_type = typename Traits::difference_type;
};

template<typename Traits>
struct nonconst_traits
{
    using value_type = typename Traits::value_type;
    using pointer = typename Traits::pointer;
    using reference = typename Traits::reference;
    using size_type = typename Traits::size_type;
    using difference_type = typename Traits::difference_type;
};

template<typename _Container, typename _Traits>
class RingBufferIterator final 
{
    friend _Container;
    public:
        using iterator_category =   std::bidirectional_iterator_tag;
        using _Self          = RingBufferIterator<_Container, _Traits>;
        using value_type     = typename _Traits::value_type;
        using pointer        = typename _Traits::pointer;
        using reference      = typename _Traits::reference;
        using size_type      = typename _Traits::size_type;
        using difference_type   = typename _Traits::difference_type;

    private:
        const _Container*   container_;
        pointer             iter_;

    public:
        RingBufferIterator()
            : container_(nullptr),
              iter_(nullptr)
        {
        }
        RingBufferIterator(const _Container* container, const pointer p)
            : container_(container),
              iter_(p)
        {
        }
        RingBufferIterator(const _Self& that)
            : container_(that.container_),
              iter_(that.iter_)
        {
        }
        RingBufferIterator(_Self&& that)
            : container_(that.container_),
              iter_(that.iter_)
        {
            that.container_ = nullptr;
            that.iter_ = nullptr;
        }
        _Self& operator= (const _Self& that)
        {
            if (this == &that)
            {
                return *this;
            }
            container_ = that.container_;
            iter_ = that.iter_;
            return *this;
        }
        _Self& operator= (_Self&& that)
        {
            operator=(that);
            that.container_ = nullptr;
            that.iter_ = nullptr;
            return *this;
        }
        ~RingBufferIterator()
        {
            container_ = nullptr;
            iter_ = nullptr;
        }

    public:
        bool operator== (const _Self& that) const
        {
            return container_ == that.container_ && iter_ == that.iter_;
        }

        bool operator!= (const _Self& that) const
        {
            return container_ != that.container_ || iter_ != that.iter_;
        }
        
        reference operator*() const
        {
            assertValid();
            return *iter_;
        }

        pointer operator-> () const
        {
            return &(operator*());
        }

        // 前置++
        _Self& operator++()
        {
            assertValid();
            container_->increment(iter_);
            if (iter_ == container_->last_)
            {
                iter_ = nullptr;
            }
            return *this;
        }

        // 后置++
        _Self operator++(int)
        {
            auto temp = *this;
            ++*this;
            return temp;
        }

        _Self& operator--()
        {
            assert(iter_ != container_->first_);
            if (iter_ == nullptr)
            {
                iter_ = container_->last_;
            }
            container_->decrement(iter_);
            return *this;
        }

        _Self operator--(int)
        {
            auto temp = *this;
            --*this;
            return temp;
        }

    private:
        void assertValid() const
        {
            assert(iter_ != nullptr && container_ != nullptr);
        }
};

template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class RingBuffer final
{
    friend class RingBufferIterator<RingBuffer<_Tp, _Alloc>, nonconst_traits<_Alloc>>;
    friend class RingBufferIterator<RingBuffer<_Tp, _Alloc>, const_traits<_Alloc>>;

    public:
        using value_type    = typename _Alloc::value_type;
        using pointer       = typename _Alloc::pointer;
        using const_pointer = typename _Alloc::const_pointer;
        using reference     = typename _Alloc::reference;
        using size_type     = typename _Alloc::size_type;
        using const_reference = typename _Alloc::const_reference;
        using difference_type = typename _Alloc::difference_type;
        using iterator      = RingBufferIterator<RingBuffer<_Tp, _Alloc>, nonconst_traits<_Alloc>>;
        using const_iterator = RingBufferIterator<RingBuffer<_Tp, _Alloc>, const_traits<_Alloc>>;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    public:
        iterator begin() { return iterator(this, empty() ? nullptr : first_); }
        const_iterator begin() const { return const_iterator(this, empty() ? nullptr : first_); }
        const_iterator cbegin() const { return const_iterator(this, empty() ? nullptr : first_); }
        // 这里用nullptr表示end迭代器, 迭代器运算的时候会特殊处理，避免赋值给了end迭代器
        iterator end() { return iterator(this, nullptr); }
        const_iterator end() const { return const_iterator(this, nullptr); }
        const_iterator cend() const { return const_iterator(this, nullptr); }

        // 这里用nullptr表示rbegin迭代器，原理同上
        reverse_iterator rbegin() { return reverse_iterator(end()); }
        const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
        const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
        reverse_iterator rend() { return reverse_iterator(begin()); }
        const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
        const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }

        size_type size() const { return size_; }
        size_type capacity() const { return end_ - start_; }
        bool empty() const { return size() == 0; }
        bool full() const { return capacity() == size(); }
        size_type reserve() const { return capacity() - size(); }

        reference operator[] (size_type index)
        {
            assert(index < size());
            return *add(first_, index);
        }

        const_reference operator[] (size_type index) const
        {
            assert(index < size());
            return *add(first_, index);
        }

        reference at(size_type index)
        {
            check_position(index);
            return (*this)[index];
        }

        const_reference cat(size_type index) const
        {
            check_position(index);
            return (*this)[index];
        }

        reference front()
        {
            assert(!empty());
            return *first_;
        }

        const_reference cfront() const
        {
            assert(!empty());
            return *first_;
        }

        reference back()
        {
            assert(!empty());
            return *((last_ == start_ ? end_ : last_) - 1);
        }

        const_reference cback() const
        {
            assert(!empty());
            return *((last_ == start_ ? end_ : last_) - 1);
        }

        void set_capacity(size_type new_capacity)
        {
            if (new_capacity == capacity())
            {
                return;
            }

            pointer buff = allocate(new_capacity);
            iterator b = begin();
            try
            {
                iterator e = b;
                if (new_capacity > size())
                {
                    e = end();
                }
                else
                {
                    for (size_t i = 0; i < new_capacity; i++)
                    {
                        e++;
                    }
                }
                reset(buff, uninitialized_copy_n_with_alloc(b, e, buff, allocator_), new_capacity);
            }
            catch(...)
            {
                deallocate(buff, new_capacity);
                throw;
            }
        }

        void swap(RingBuffer<_Tp, _Alloc>& that)
        {
            // 不处理allocator
            std::swap(start_, that.start_);
            std::swap(end_, that.end_);
            std::swap(first_, that.first_);
            std::swap(last_, that.last_);
            std::swap(size_, that.size_);
        }

        void push_back(const_reference item)
        {
            if (full())
            {
                if (empty())
                {
                    return;
                }
                replace(last_, item);
                increment(last_);
                // 满了的情况下first_一定是等于last_的, 这里第一个元素被覆盖，第二个元素变成第一个元素
                first_ = last_;
            }
            else
            {
                allocator_.construct(last_, item);
                increment(last_);
                ++size_;
            }
        }

        void push_front(const_reference item)
        {
            try
            {
                if (full())
                {
                    if (empty())
                    {
                        return;
                    }
                    decrement(first_);
                    replace(first_, item);
                    last_ = first_;
                }
                else
                {
                    decrement(first_);
                    // construct里面可能会抛出异常，所以需要恢复first_的位置
                    allocator_.construct(first_, item);
                    ++size_;
                }
            }
            catch(...)
            {
                increment(first_);
                throw;
            }
        }

        template<typename... Args>
        void emplace_back(Args&&... args)
        {
            if (full())
            {
                if (empty())
                {
                    return;
                }
                replace(last_, std::forward<Args>(args)...);
                increment(last_);
                // 满了的情况下first_一定是等于last_的, 这里第一个元素被覆盖，第二个元素变成第一个元素
                first_ = last_;
            }
            else
            {
                allocator_.construct(last_, std::forward<Args>(args)...);
                increment(last_);
                ++size_;
            }
        }

        void pop_back()
        {
            assert(!empty());
            decrement(last_);
            destroy_item(last_);
            --size_;
        }

        void pop_front()
        {
            assert(!empty());
            destroy_item(first_);
            increment(first_);
            --size_;
        }

        void clear()
        {
            destroy_content();
            size_ = 0;
        }

        iterator erase(iterator pos)
        {
            pos.assertValid();
            pointer next = pos.iter_;
            increment(next);
            for (pointer p = pos.iter_; next != last_; p = next, increment(next))
            {
                replace(p, *next);
            }
            decrement(last_);
            destroy_item(last_);
            --size_;
            return last_ == pos.iter_ ? end() : pos;
        }

    private:
        size_type max_size() const
        {
            return std::min<size_type>(allocator_.max_size(), std::numeric_limits<difference_type>::max());
        }

        void replace(pointer pos, const value_type& item)
        {
            *pos = item;
        }

        template<typename... Args>
        void replace(pointer pos, Args&&... args)
        {
            *pos = std::move(_Tp(std::forward<Args>(args)...));
        }

        template <typename Pointer>
        void increment(Pointer& p) const
        {
            if (++p == end_)
            {
                p = start_;
            }
        }

        template <typename Pointer>
        void decrement(Pointer& p) const
        {
            if (p == start_)
            {
                p = end_;
            }
            --p;
        }

        template <typename Pointer>
        pointer add(Pointer p, difference_type n) const
        {
            return p + (n < (end_ - p) ? n : (n - capacity()));
        }

        template <typename Pointer>
        pointer sub(Pointer p, difference_type n) const
        {
            return p - (n > (p - start_) ? (n - capacity()) : n);
        }

        void check_position(size_type index) const
        {
            if (index >= size())
            {
                throw clusnet::base::Exception("ring_buffer_out_of_range");
            }
        }

    private:
        void initialize_buffer(size_type n)
        {
            start_ = allocate(n);
            end_ = start_ + n;
        }

        void initialize_buffer(size_type n, const_reference item)
        {
            initialize_buffer(n);
            try
            {
                uninitialized_fill_n_with_alloc(start_, size(), item, allocator_);
            }
            catch (...)
            {
                deallocate(start_, size());
                throw;
            }
        }

        pointer allocate(size_type n)
        {
            if (n > max_size())
            {
                throw clusnet::base::Exception("ring_buffer_length_error");
            }
            return (n == 0) ? nullptr : allocator_.allocate(n);
        }

        void deallocate(pointer p, size_type n)
        {
            if (p != nullptr)
            {
                allocator_.deallocate(p, n);
            }
        }

        void destroy_item(pointer p)
        {
            allocator_.destroy(p);
        }

        void destroy_content()
        {
            for (size_type i = 0; i < size(); ++i, increment(first_))
            {
                destroy_item(first_);
            }
        }

        void destroy()
        {
            destroy_content();
            deallocate(start_, capacity());
            start_ = nullptr;
            end_ = nullptr;
            first_ = nullptr;
            last_ = nullptr;
            size_ = 0;
        }

        void reset(pointer buff, pointer last, size_type new_capacity)
        {
            destroy();
            size_ = last - buff;
            first_ = start_ = buff;
            end_ = start_ + new_capacity;
            last_ = last == end_ ? start_ : last;
        }

    public:
        RingBuffer(const RingBuffer<_Tp, _Alloc>& that)
            : size_(that.size()),
              allocator_(that.allocator_)
        {
            initialize_buffer(that.capacity());
            first_ = start_;
            try
            {
                last_ = uninitialized_copy_n_with_alloc(that.begin(), that.end(), start_, allocator_);
            }
            catch (...)
            {
                deallocate(start_, that.capacity());
            }
            // make sure circular
            if (last_ == end_)
            {
                last_ = start_;
            }
        }

        RingBuffer(RingBuffer<_Tp, _Alloc>&& that)
            : start_(that.start_),
              end_(that.end_),
              first_(that.first_),
              last_(that.last_),
              size_(that.size()),
              allocator_(std::move(that.allocator_))
        {
            that.start_ = that.end_ = that.first_ = that.last_ = nullptr;
            that.size_ = 0;

            if (last_ == end_)
            {
                last_ = start_;
            }
        }

        explicit RingBuffer(size_type n, const _Alloc& allocator = _Alloc())
            : size_(0),
              allocator_(allocator)
        {
            initialize_buffer(n);
            first_ = last_ = start_;
        }

        RingBuffer(size_type n, const_reference item, const _Alloc& allocator = _Alloc())
            : size_(n),
              allocator_(allocator)
        {
            initialize_buffer(n, item);
            first_ = last_ = start_;
        }

        RingBuffer<_Tp, _Alloc>& operator= (const RingBuffer<_Tp, _Alloc>& that)
        {
            if (this == &that)
            {
                return *this;
            }
            pointer buff = allocate(that.capacity());
            try
            {
                reset(buff, uninitialized_copy_n_with_alloc(that.begin(), that.end(), buff, allocator_), that.capacity());
                // 不处理allocator_
            }
            catch (...)
            {
                deallocate(buff, that.capacity());
                throw;
            }
            return *this;
        }

        RingBuffer<_Tp, _Alloc>& operator= (RingBuffer<_Tp, _Alloc>&& that)
        {
            if (this == &that)
            {
                return *this;
            }
            destroy();
            start_ = that.start_;
            end_ = that.end_;
            first_ = that.first_;
            last_ = that.last_;
            size_ = that.size_;
            // 不处理allocator_

            that.start_ = that.end_ = that.first_ = that.last_ = nullptr;
            that.size_ = 0;

            if (last_ == end_)
            {
                last_ = start_;
            }
            return *this;
        }

        ~RingBuffer()
        {
            destroy();
        }


    private:
        pointer     start_;         // 内部buffer的起始位置
        pointer     end_;           // 内部buffer的结束位置
        pointer     first_;         // ringbuffer的虚拟起始位置
        pointer     last_;          // ringbuffer的虚拟结束位置(one behind the last element)
        size_type   size_;
        _Alloc      allocator_;
};

template<typename _Tp, typename _Alloc>
inline bool operator== (const RingBuffer<_Tp, _Alloc>& _x,  const RingBuffer<_Tp, _Alloc>& _y)
{
    return _x.size() == _y.size() && std::equal(_x.begin(), _x.end(), _y.begin());
}

template<typename _Tp, typename _Alloc>
inline bool operator!= (const RingBuffer<_Tp, _Alloc>& _x, const RingBuffer<_Tp, _Alloc>& _y)
{
    return !(_x == _y);
}

template<typename _Tp, typename _Alloc>
inline void swap(RingBuffer<_Tp, _Alloc>& _x, RingBuffer<_Tp, _Alloc>& _y)
{
    return _x.swap(_y);
}

}
}

#endif 
